#include "Triangulate.h"
#include ".\triangulation\poly2tri.h"

namespace LightPlayer{

	static const float EPSILON=0.0000000001f;

	float Triangulate::Area(const Vector2dVector &contour)
	{

	  int n = contour.size();

	  float A=0.0f;

	  for(int p=n-1,q=0; q<n; p=q++)
	  {
		A+= contour[p].GetX()*contour[q].GetY() - contour[q].GetX()*contour[p].GetY();
	  }
	  return A*0.5f;
	}


	void Triangulate::Bounds( const Vector2dVector &contour, vec2& o_min, vec2& o_max )
	{
		int n = contour.size();
		if( n > 0)
		{
			o_min = contour[0];
			o_max = contour[0];

			for(int i=0; i<n; i++ )
			{
				o_min.x = min( o_min.x, contour[i].x );
				o_min.y = min( o_min.y, contour[i].y );

				o_max.x = max( o_max.x, contour[i].x );
				o_max.y = max( o_max.y, contour[i].y );
			}
		}
	}


	/*
		InsideTriangle decides if a point P is Inside of the triangle
		defined by A, B, C.
	*/
	bool Triangulate::InsideTriangle(float Ax, float Ay,
						  float Bx, float By,
						  float Cx, float Cy,
						  float Px, float Py)

	{
	  float ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
	  float cCROSSap, bCROSScp, aCROSSbp;

	  ax = Cx - Bx;  ay = Cy - By;
	  bx = Ax - Cx;  by = Ay - Cy;
	  cx = Bx - Ax;  cy = By - Ay;
	  apx= Px - Ax;  apy= Py - Ay;
	  bpx= Px - Bx;  bpy= Py - By;
	  cpx= Px - Cx;  cpy= Py - Cy;

	  aCROSSbp = ax*bpy - ay*bpx;
	  cCROSSap = cx*apy - cy*apx;
	  bCROSScp = bx*cpy - by*cpx;

	  return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
	};

	bool Triangulate::Snip(const Vector2dVector &contour,int u,int v,int w,int n,int *V)
	{
	  int p;
	  float Ax, Ay, Bx, By, Cx, Cy, Px, Py;

	  Ax = contour[V[u]].GetX();
	  Ay = contour[V[u]].GetY();

	  Bx = contour[V[v]].GetX();
	  By = contour[V[v]].GetY();

	  Cx = contour[V[w]].GetX();
	  Cy = contour[V[w]].GetY();

	  if ( EPSILON > (((Bx-Ax)*(Cy-Ay)) - ((By-Ay)*(Cx-Ax))) ) return false;

	  for (p=0;p<n;p++)
	  {
		if( (p == u) || (p == v) || (p == w) ) continue;
		Px = contour[V[p]].GetX();
		Py = contour[V[p]].GetY();
		if (InsideTriangle(Ax,Ay,Bx,By,Cx,Cy,Px,Py)) return false;
	  }

	  return true;
	}

	bool Triangulate::Process(const Vector2dVector &contour,Vector2dVector &result)
	{
	  /* allocate and initialize list of Vertices in polygon */

	  int n = contour.size();
	  if ( n < 3 ) return false;

	  int *V = new int[n];

	  /* we want a counter-clockwise polygon in V */

	  if ( 0.0f < Area(contour) )
		for (int v=0; v<n; v++) V[v] = v;
	  else
		for(int v=0; v<n; v++) V[v] = (n-1)-v;

	  int nv = n;

	  /*  remove nv-2 Vertices, creating 1 triangle every time */
	  int count = 2*nv;   /* error detection */

	  for(int m=0, v=nv-1; nv>2; )
	  {
		/* if we loop, it is probably a non-simple polygon */
		if (0 >= (count--))
		{
		  //** Triangulate: ERROR - probable bad polygon!
		  delete V;
		  return false;
		}

		/* three consecutive vertices in current polygon, <u,v,w> */
		int u = v  ; if (nv <= u) u = 0;     /* previous */
		v = u+1; if (nv <= v) v = 0;     /* new v    */
		int w = v+1; if (nv <= w) w = 0;     /* next     */

		if ( Snip(contour,u,v,w,nv,V) )
		{
		  int a,b,c,s,t;

		  /* true names of the vertices */
		  a = V[u]; b = V[v]; c = V[w];

		  /* output Triangle */
		  result.push_back( contour[a] );
		  result.push_back( contour[b] );
		  result.push_back( contour[c] );

		  m++;

		  /* remove v from remaining polygon */
		  for(s=v,t=v+1;t<nv;s++,t++) V[s] = V[t]; nv--;

		  /* reset error detection counter */
		  count = 2*nv;
		}
	  }



	  delete V;

	  return true;
	}

	bool Triangulate::ProcessP2T( const Path &contour, Vector2dVector &result )
	{
		result.clear();

		using namespace p2t;
		bool succeed = false;

		array<vec2> borders;
		contour.getBorderResolved(borders,true,true);
		
		if( borders.size() >= 3 ){
			vector<Point*> polyline;
			vector< vector<Point*> > ListHoles;
			// construct border
			for (uint32 i=0; i<borders.size(); i++){
				polyline.push_back(new Point(borders[i].x,borders[i].y));
			}
			// construct list of hole
			for (uint32 i=0; i < contour.getHoles().size(); i++){
				array<Point*> temp;
				array<vec2> hole_borders;
				contour.getHoles().at(i)->getBorderResolved(hole_borders,true,true,true);
				if( hole_borders.size() >= 3 ){
					for (uint32 j=0; j<hole_borders.size(); j++){
						temp.push_back(new Point(hole_borders[j].x,hole_borders[j].y));
					}
					ListHoles.push_back( temp );
				}
			}


			CDT cdt(polyline);
			for (uint32 i=0; i<ListHoles.size(); i++){
				cdt.AddHole( ListHoles[i] );
			}
			cdt.Triangulate();
			
			vector<Triangle*> triangles = cdt.GetTriangles();
			for (uint32 i=0; i<triangles.size(); i++){
				result.push_back( vec2( (float)triangles[i]->GetPoint( 0 )->x, (float)triangles[i]->GetPoint( 0 )->y) );
				result.push_back( vec2( (float)triangles[i]->GetPoint( 1 )->x, (float)triangles[i]->GetPoint( 1 )->y) );
				result.push_back( vec2( (float)triangles[i]->GetPoint( 2 )->x, (float)triangles[i]->GetPoint( 2 )->y) );
			}

			if(result.size() >= 3){
				succeed = true;
			}

			// delete memory !!!!
			for (uint32 i=0; i<polyline.size(); i++){
				delete polyline[i];
			}
			for (uint32 i=0; i<ListHoles.size(); i++){
				for (uint32 j=0; j< ListHoles[i].size() ; j++){
					delete ListHoles[i][j];
				}
			}
			ListHoles.clear();
			polyline.clear();
		}


		return succeed;
	}

};